package leetcode_周赛._2022._202203;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/13 10:49
 * 2022/03/13 周赛
 * 做出两题
 */
public class _13 {

    /**
     * 5203
     * 算法：模拟
     * @param n
     * @param artifacts
     * @param dig
     * @return
     */
    public int digArtifacts(int n, int[][] artifacts, int[][] dig) {
        int ans = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] d : dig) {
            List<Integer> list = map.getOrDefault(d[0], new ArrayList<>());
            list.add(d[1]);
            map.put(d[0], list);
        }
        for (int[] artifact : artifacts) {
            boolean flag = true;
            for (int i = artifact[0]; i <= artifact[2]; i++) {
                List<Integer> list = map.getOrDefault(i, new ArrayList<>());
                if (list.isEmpty()) {
                    flag = false;
                    break;
                }
                for (int j = artifact[1]; j <= artifact[3]; j++) {
                    if (!list.contains(j)) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) ++ans;
        }
        return ans;
    }

    /**
     * 5227
     * 算法：贪心
     * 分类讨论
     * 将前面的 k-1 个元素取出
     * 最后一次操作：比较之前取出的元素的最大值和当前栈顶元素的值和栈顶元素的下一个元素的值
     * 当数组长度为 1 时，如果 k 是奇数，则会把栈中元素拿空，返回 -1
     * k > nuns.length 时，将所有元素取出
     * k < nums.length 时，取出前 k - 1 个元素
     * k == nums.length 时，取出 k - 1 个元素，将最大的元素放回栈中
     * @param nums
     * @param k
     * @return
     */
    public int maximumTop(int[] nums, int k) {
        int len = nums.length;
        if (len == 1 && k % 2 != 0) return -1;
        int ans = 0;
        if (k > len) for (int num : nums) ans = Math.max(ans, num);
        else if (k == len) for (int i = 0; i < len - 1; i++) ans = Math.max(ans, nums[i]);
        else {
            for (int i = 0; i < k - 1; i++) ans = Math.max(ans, nums[i]);
            ans = Math.max(ans, nums[k]);
        }
        return ans;
    }


}
